/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-26 14:09:31
 * @LastEditors: lily
 * @LastEditTime: 2021-05-26 15:00:07
 */
/*
 * @lc app=leetcode.cn id=304 lang=javascript
 *
 * [304] 二维区域和检索 - 矩阵不可变
 */

// @lc code=start

//  思想：前缀和
//  sum(r1,c1,r2,c2) = preSum[r2][c2] + preSum[r1-1][c1-1] 
//                   + preSum[r2][c1-1] + preSum[r1-1][c2] 
//  303题目升级

// 复杂度： O(mn) O(mn)  查询O(1)

/**
 * @param {number[][]} matrix
 */
var NumMatrix = function (matrix) {
    const rl = matrix.length, cl = matrix[0].length
    let rows = !rl ? 1 : rl + 1, cols = !cl ? 1 : cl + 1
    let preSum = Array.from(new Array(rows), () => new Array(cols).fill(0))
    // 设定前缀和数组
    for (let i = 1; i < rl + 1; i++) {
        for (let j = 1; j < cl + 1; j++) {
            preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1]
        }
    }
    this.preSum = preSum
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
    return this.preSum[row2 + 1][col2 + 1] + this.preSum[row1][col1] - this.preSum[row2 + 1][col1] - this.preSum[row1][col2 + 1]
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = new NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */
// @lc code=end

let matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5]
]
var obj = new NumMatrix(matrix)
console.log(obj.sumRegion(2, 1, 4, 3));
console.log(obj.sumRegion(1, 1, 2, 2));
console.log(obj.sumRegion(1, 2, 2, 4));